package nowcoder.dynamic;

// 删除至少几个字符可以变成另一个字符串的子串
// 给定两个字符串s1和s2
// 返回s1至少删除多少字符可以成为s2的子串
public class MinDelete {

    public int minDelete1(String s1, String s2) {
        return f(s1.toCharArray(), s2.toCharArray(), 0, 0);
    }

    public int f(char[] s1, char[] s2, int i, int j) {

        if (i >= s1.length) {
            if (j >= s2.length) {
                return 0;
            } else {
                return Integer.MAX_VALUE;
            }
        } else {
            if (j >= s2.length) {
                return (s1.length - i);
            }
        }

        if (s1[i] == s2[j]) {
            return f(s1, s2, i + 1, j + 1);
        }

        return f(s1, s2, i + 1, j) + 1;
    }

    public static void main(String[] args) {
        MinDelete minDelete = new MinDelete();
        System.out.println("minDelete.minDelete1(\"abc\", \"ac\") = " + minDelete.minDelete1("abc", "ac"));
        System.out.println("minDelete.minDelete1(\"abd\", \"ac\") = " + minDelete.minDelete1("abd", "ac"));
        System.out.println("minDelete.minDelete1(\"abdc\", \"ac\") = " + minDelete.minDelete1("abdc", "ac"));

    }

}
